/**
 * @a https://leetcode.cn/problems/subarray-sums-divisible-by-k/
 */

#include "common.h"

class Solution
{
public:
    int subarraysDivByK(vector<int> &nums, int k)
    {
        unordered_map<int, int> hash;

        int sum = 0, ret = 0;
        hash[sum % k] = 1; /*sum == 0*/
        for (const auto num : nums)
        {
            sum += num; int find = (sum % k + k) % k;
            if (hash.count(find)) ret += hash[find];
            ++hash[find];
        }
        return ret;
    }
};